package 二叉树层序遍历.二叉树的层平均值;

import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.Collections;
import java.util.List;

public class Solution {
    /*
    给定一个非空二叉树的根节点 root , 以数组的形式返回每一层节点的平均值。与实际答案相差 10-5 以内的答案可以被接受。
     */
    public List<Double> averageOfLevels(TreeNode root) {
        // 层序遍历

        if(root == null)
            return Collections.emptyList();
        List<Double> result = new ArrayList<>();
        ArrayDeque<TreeNode> queue = new ArrayDeque<>();
        TreeNode p, last = root;
        queue.offer(root);
        double levelSum = 0.0;
        int count = 0;
        while (!queue.isEmpty()) {
            p = queue.poll();
            count++;
            levelSum += p.val;
            if(p.left!=null) queue.offer(p.left);
            if(p.right!=null) queue.offer(p.right);
            if(p == last){
//                double avg = Double.parseDouble(String.format("%.5f", levelSum / count));
                double avg = levelSum / count;
                result.add(avg);
                last = queue.peekLast();
                levelSum = 0.0;
                count = 0;
            }
        }
        return result;
    }
}
